(파이썬 S/W 문제해결 기본) List1 - 4828번 4831번 4834번 4835번

4828번 - min max

• 시간 : 10개 테스트케이스를 합쳐서 Python의 경우 2초
• 메모리 : 힙, 정적 메모리 합쳐서 256MB 이내, 스택 메모리 1MB 이내

한 줄을 한번에 입력 받는 input() 말고 띄어쓰기 마다 입력받는 방법이 없을까?
sys.stdin.readline() 을 사용하면 시간 단축은 많이 된다는 것 같다

import sys

T = int(input()) # 1 <= T <= 50

for test_case in range(1, T+1):
N = int(input()) # 5 <= N <= 1000
max = 1; min = 1000000 # 1<= a <= 1000000
a = [int(num) for num in sys.stdin.readline().split()] # = [int(num) for num in input().split()] # = list(map(int, input().split()))

    for num in a:
        if num>max:
            max = num
        if num<min:
            min = num

    print("#{} {}".format(test_case, max-min))

---

4831번 - 전기버스

• 시간 : 10개 테스트케이스를 합쳐서 Python의 경우 2초
• 메모리 : 힙, 정적 메모리 합쳐서 256MB 이내, 스택 메모리 1MB 이내

자동차경주대회 문제랑 비슷

T = int(input()) # 1 <= T <= 50

for test_case in range(1, T+1):
K, N, M = map(int, input().split()) # k:최대 이동 거리, n:총 정거장 수 , m:충전기 정류장 수
bus_stop = [int(stop) for stop in input().split()]
charge_stop = [0]\*(N+1)
for i in range(M):
charge_stop[bus_stop[i]] = 1

    bus_position = 0
    max_stop = K
    cnt=0

    while True:
        check = 0
        for i in range(bus_position+1, max_stop+1):
            if charge_stop[i] == 1:
                bus_position = i
            else:
                check += 1

        if check == K:
            cnt = 0
            break

        cnt += 1
        max_stop = bus_position + K

        if max_stop >= N:
            break

    print('#%s %d'%(test_case, cnt))

---

4834번 - 숫자 카드

• 시간 : 10개 테스트케이스를 합쳐서 Python의 경우 2초
• 메모리 : 힙, 정적 메모리 합쳐서 256MB 이내, 스택 메모리 1MB 이내

카드 장수가 같을 때 큰 숫자를 선택해야하는 조건을 주의

T = int(input()) # 1 <= T <= 50

for test_case in range(1, T+1):
N = int(input()) # 5 <= N <= 100
a = [int(num) for num in input()] # 0 <= a <= 9

    cards = [0] * 10
    max_cnt = 0
    max_idx = 0

    for i in range(N):
        cards[a[i]] += 1

        if cards[a[i]] > max_cnt:
            max_cnt = cards[a[i]]
            max_idx = a[i]
        elif cards[a[i]] == max_cnt:
            if a[i] > max_idx:
                max_idx = a[i]

    print("#{} {} {}".format(test_case, max_idx, max_cnt))

---

4835번 - 구간 합

• 시간 : 10개 테스트케이스를 합쳐서 Python의 경우 2초
• 메모리 : 힙, 정적 메모리 합쳐서 256MB 이내, 스택 메모리 1MB 이내

시간복잡도 : 정렬 sort() - O(nlogn)

최대,최소 max(),min() - O(n)

T = int(input()) # 1 <= T <= 50

for test_case in range(1, T+1):
N, M = map(int, input().split()) # 10 <= N <= 100 , 2 <= M <= N
a = [int(num) for num in input().split()] # 1 <= a <= 10000

    sum_list = []
    for i in range(N - M + 1):
        sum_list.append(sum(a[i:i + M]))

    print("#{} {}".format(test_case, max(sum_list) - min(sum_list)))

---